// // 线性表（a1,a2,a3,…,an）中元素递增有序且按照顺序存储于计算机内。
// // 要求设计一个算法完成：
// // （1）用最少的时间在表中查找数值为 x 的元素。
// // （2）若查找到将其与后继元素位置交换。
// // （3）若找不到将其插入表中并使表中元素仍然递增有序。
//
// #include <stdio.h>
// #include <stdlib.h>
// #include <windows.h>
//
// #define INIT_SIZE 4  // 更合理的初始大小
//
// typedef struct SqList {
//     int* data;
//     int length;
//     int maxsize;
// } SqList;
//
// void InitSq(SqList* L) {
//     L->data = NULL;  // 修正：使用赋值运算符 =
//     L->length = 0;
//     L->maxsize = 0;
// }
//
// void FullSq(SqList* L) {
//     if (L->length == L->maxsize) {
//         int NewMaxsize = L->maxsize == 0 ? INIT_SIZE : 2 * L->maxsize;
//         int* tmp = (int*)realloc(L->data, sizeof(int) * NewMaxsize);  // 修正：去掉多余的 2*
//         if (tmp == NULL) {
//             perror("内存分配失败");
//             exit(EXIT_FAILURE);
//         }
//         L->data = tmp;
//         L->maxsize = NewMaxsize;
//     }
// }
//
// void InsertBack(SqList* L, int elem) {
//     if (L == NULL) return;
//     FullSq(L);
//     L->data[L->length] = elem;
//     L->length++;
// }
//
// void PrintSq(SqList* L) {
//     if (L == NULL || L->data == NULL) return;
//     for (int i = 0; i < L->length; i++) {
//         printf("%d ", L->data[i]);
//     }
//     printf("\n");
// }
//
// void DestroySq(SqList* L) {
//     if (L == NULL) return;
//     free(L->data);  // 修正：实际释放内存
//     L->data = NULL;  // 修正：使用赋值运算符 =
//     L->length = 0;
//     L->maxsize = 0;
//     // 不需要 L = NULL，因为参数是局部副本
// }
//
// //折半查找实现
// void ZheBan(SqList* L,int x) {
//     int low=0;
//     int high=L->length-1;
//     int mid=-1;
//     int found=0;
//     while (low<=high) {
//         mid=(low+high)/2;
//         if(L->data[mid]==x) {
//             found=1;
//             break;
//         }
//         else if(L->data[mid]<x) {
//             low=mid+1;
//         }
//         else {
//             high=mid-1;
//         }
//     }
//     if(found==1) {
//         if(mid<L->length-1) {
//             int temp=L->data[mid];
//             L->data[mid]=L->data[mid+1];
//             L->data[mid+1]=temp;
//         }
//     }else {
//         InsertBack(L,x);
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     SqList L;
//     InitSq(&L);
//
//     InsertBack(&L,1);
//     InsertBack(&L,3);
//     InsertBack(&L,5);
//     InsertBack(&L,7);
//     InsertBack(&L,9);
//     PrintSq(&L);
//
//     printf("最初表\n");
//     PrintSq(&L);
//
//     ZheBan(&L,5);
//     printf("可查到的情况\n");
//     PrintSq(&L);
//
//     ZheBan(&L,20);
//     printf("查不到的情况\n");
//     PrintSq(&L);
//
//     DestroySq(&L);
//
//     return 0;
// }
//
// // 【算法思想】顺序存储的线性表递增有序，可以顺序查找，也可以折半查找。
// // 题目要求采用“最少的时间在表中查找数值为 x 的元素”，应使用折半查找